//1186.删除一次得到子数组最大和
//https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        //dp[i][k] 表示以arr[i]结尾删除k次的子数组最大值
        //dp[0][0] 表示以arr[i]结尾删除0次 即arr[0]
        //dp[0][1] 表示以arr[i]结尾删除1次 为0
        int n = arr.size();
        if(n == 0) return 0;
        int dp0 = arr[0],dp1 = 0,ret = arr[0];
        for(int i = 1;i<n;++i)
        {
            //注意先更新删除的情况 会用到上一次不删除的情况
            //如果选择 要么删除当前的arr[i]要么选择已经删除的子数字 取最大值
            dp1 = max(dp0,dp1+arr[i]);
            //如果不删除 则当前arr[i]与前dp[i-1][0]进行对比 取最大的子数组的值
            dp0 = max(dp0,0)+arr[i];
            ret = max(ret,max(dp0,dp1));
        }
        return ret;
    }
};